1. Field of the Invention
The present invention relates generally to the field of signal processing. More specifically, the present invention relates to an apparatus and method for compressing and decompressing digital image files.
2. The Background Art
Various image compression/decompression systems are well known to those of ordinary skill in the art. FIG. 1 is a top-level block diagram depicting an exemplary image compression/decompression system 100 in the context of the present invention. As shown in FIG. 1, exemplary image compression/decompression system 100 comprises an encoder 110, a decoder 120, and a channel 130. Exemplary hardware architecture for an image compression computer system suitable for implementing an encoder 110 as shown in FIG. 1 will be described later in this document with reference to FIG. 2A. From a functional standpoint, encoder 110 comprises an input file 112, which is processed by an image compressor 115. Further details regarding various aspects of image compressor 115 will be provided throughout this document.
Still referring to FIG. 1, image compressor 115 produces a compressed file 135 that is transmitted via a channel 130 to an image decompressor 125 at a decoder 120. The channel 130 may comprise a switched backbone such as the network commonly referred to as the Internet, any local or wide area network, or may simply comprise storage of the compressed file 135 into any suitable medium such as a hard drive, flash memory, CD-ROM disk, and/or floppy disk. From a functional standpoint, image decompressor 125 attempts to recreate the original input file 112 and produces an output image file 127 which may be stored on any suitable medium and/or displayed (e.g., on a screen, printer, etc.). Exemplary hardware architecture for an image decompression computer system suitable for implementing a decoder 120 as shown in FIG. 1 will be described later in this document with reference to FIG. 2B. Further details regarding various aspects of image decompressor 125 will be provided throughout this document.
As will be recognized by those of ordinary skill in the art, when the output file generated by image decompressor 125 is identical (or essentially identical, within the tolerances of each particular implementation) to the original input file 112, the image compression system 100 is said to be xe2x80x9clossless.xe2x80x9d On the other hand, when the output file generated by image decompressor 125 is different from (e.g., contains less information or detail than) the original input file 112, the image compression system 100 is said to be xe2x80x9clossy.xe2x80x9d As will also be recognized by those of ordinary skill in the art, without limitation, lossiness may be due to transmission of fewer pixels than the number of pixels present in the original image, to transmission of less spatial frequency information than is present in the original image, to quantization of intensity and/or color levels to fewer intensities and/or colors than are present in the original image, or to various combinations of the above factors. As will be described in more detail later in this document, embodiments of the present invention may implement either lossless or lossy image compression.
Currently, various types of wireless communication devices such as Personal Digital Assistants (xe2x80x9cPDAsxe2x80x9d) and cellular telephone handsets are beginning to support the transmission and reception of graphic images via data communication networks (such as the Internet). Data communication networks used to transmit such graphic images typically have significant bandwidth limitations, and such wireless communication devices typically exhibit significant limitations in terms of available processing power and memory. Moreover, current xe2x80x9cstandardxe2x80x9d image compression/decompression systems known to those of ordinary skill in the art (e.g., JPEG, GIF, PNG) either exhibit a relatively low compression ratio or require relatively high processing power and/or memory at the image compressor and/or decompressor. Similarly, current xe2x80x9cnon-standardxe2x80x9d image compression/decompression systems known to those of ordinary skill in the art (e.g., Binary Tree Predictive Coding, or xe2x80x9cBTPCxe2x80x9d) require high processing power and/or memory at the image compressor while its compression ratio is typically comparable to JPEG for natural Images and typically worse than GIF or PNG for graphics. Finally, image compression/decompression systems known to those of ordinary skill in the art typically exhibit good performance for a particular general class of image files (e.g., bilevel, grayscale, or color files), but exhibit relatively poor performance for one or more of the other general classes of image files.
Thus, there exists a need for an image compression/decompression apparatus and method which exhibits a high compression ratio while conserving transmission bandwidth, as well as conserving processing power and memory at the image compressor and/or decompressor, and which exhibits good performance across a broad spectrum of general image file classes. The present invention addresses this need. These and other features and advantages of the present invention will be presented in more detail in the following specification of the invention and in the associated figures.
An apparatus and method for compressing and decompressing digital image files is described. At the image encoder/compressor, an input image file, which may be of bilevel, grayscale, or color file type, is subdivided into one or more sub-images. Each sub-image may be separately compressed. In the case of grayscale or color input images, the input image may be pre-processed using a threshold parameter to quantize the intensity and/or color vectors into a compressed palette of intensities and/or color vectors. A forward transform is performed on each pre-processed sub-image, based on a binary quincunx image pyramid and a set of pixel value prediction equations. The output of the forward transform comprises a set of prediction error signals and a coarse low-band signal. Each of the prediction error signals and the coarse low-band signal are run length and/or tree encoded, and all of the outputs of the run length and/or tree encoders are combined into a single array, which is encoded using a Huffman coding algorithm or arithmetic coding algorithm. The output of the Huffman encoder or arithmetic encoder is written to a compressed output file in a format conducive to image reconstruction at the image decompressor. The compressed output file is stored and/or transmitted to an image decoder/decompressor. At the image decoder/decompressor, the encoding/compression process is reversed to generate a decompressed image file, which may be stored and/or displayed as appropriate. Embodiments of the system may implement either lossless compression or lossy compression, where lossiness may be due to transmission of fewer pixels than those present in the original image and/or by quantization of the pixel intensities and/or color vectors into fewer intensity/color levels than those present in the original image.